//
//  148. 排序链表.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/23.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution148_2 {
    // 排序链表
    // 采用归并排序
    // 1. 分成两段
    // 2. 排序段
    // 3. 合并两段
    func sortList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        let midPre = findMidPre(head)
        let head2 = midPre?.next
        midPre?.next = nil
        return mergeTowList(one: sortList(head), tow: sortList(head2))
    }
    // 合并两个有序链表
    func mergeTowList(one: ListNode?, tow: ListNode?) -> ListNode? {
        let vHead = ListNode(-1)
        var p: ListNode? = vHead
        var p1 = one
        var p2 = tow
        while p1 != nil && p2 != nil {
            if p1!.val <= p2!.val {
                p?.next = p1
                p1 = p1?.next
            } else {
                p?.next = p2
                p2 = p2?.next
            }
            p = p?.next
        }
        if p1 != nil {
            p?.next = p1
        }
        if p2 != nil {
            p?.next = p2
        }
        return vHead.next
    }
    // 寻找中间节点(这是最好的写法)
    func findMidPre(_ head: ListNode?) -> ListNode? {
        let vHead = ListNode(-1)
        vHead.next = head
        var slow: ListNode? = vHead
        var fast: ListNode? = vHead
        while fast != nil {
            if fast?.next == nil {
                break
            }
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow
    }
    static func test() {
        let head = [4,2,1,3]
        let root = createNode(head)
        let solution = Solution148_2()
        let result = solution.sortList(root)
        print(result)
    }
    
    static func createNode(_ link: [Int]) -> ListNode?{
        var root: ListNode?
        var p: ListNode?
        for item in link {
            if root == nil {
                root = ListNode(item)
                p = root
            } else {
                p?.next = ListNode(item)
                p = p?.next
            }
        }
        return root
    }
}
